package com.stanley.alogrithm.sorts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class GetLeastNumbers {

    public static void main(String[] args) {
        Class c1 = new ArrayList<String>().getClass();
        Class c2 = new ArrayList<Integer>().getClass();
        System.out.println("c1==c2 ? " + (c1 == c2));

        int[] testData = {4,5,1,6,2,7,3,8,0 };
        GetLeastNumbers solution = new GetLeastNumbers();
        ArrayList<Integer> result = solution.GetLeastNumbers_Solution(testData, 4);
        System.out.println("result:" + result);
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        ArrayList result = new ArrayList<>(k);
        if (input == null || k == 0 || k > input.length) {
            return result;
        }

        //Arrays.sort(input);
        for (int i = 0; i < input.length; i++) {
            if(queue.size() != k) {
                queue.offer(input[i]);
            } else {
                if(input[i] < queue.peek()) {
                    queue.poll();
                    queue.offer(input[i]);
                }
            }
        }
        //int len = queue.size();

        while(!queue.isEmpty()) {
            result.add(queue.peek());
            queue.poll();
        }

//        for (Integer v: queue) {
//            result.add(v);
//        }

        return result;
    }
}
